#include<bits/stdc++.h>
using namespace std;
const int N=105;

int n,m;
int edges[N][N];
int edges2[N][N];
int ans=INT_MAX;

int main(){
    scanf("%d%d",&n,&m);
    memset(edges,0x3f,sizeof(edges));
    for(int i=1;i<=n;i++){
        edges[i][i]=0;
    }
    for(int i=1;i<=m;i++){
        int s,t,w;
        scanf("%d%d%d",&s,&t,&w);
        edges[s][t]=edges[t][s]=w;
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(edges[i][k]+edges[k][j]<edges[i][j])
                {
                    edges[i][j]=edges[i][k]+edges[k][j];
                }
            }
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            //copy
            for(int r=1;r<=n;r++){
                for(int c=r;c<=n;c++){
                    edges2[r][c]=edges2[c][r]=edges[r][c];
                }
            }
            edges2[i][j]=edges2[j][i]=0;
            //
            const int kk[]={i,j};
            for(int p=0;p<2;p++){
                int k=kk[p];
                for(int r=1;r<=n;r++){
                    for(int c=1;c<=n;c++){
                        if(edges2[r][c]>edges2[r][k]+edges2[k][c]){
                            edges2[r][c]=edges2[r][k]+edges2[k][c];
                        }
                    }
                }
            }
            // for(int k=1;k<=n;k++){
            //     if(edges2[i][k]<edges2[j][k]){
            //         edges2[j][k]=edges2[k][j]=edges2[i][k];
            //     }else{
            //         edges2[i][k]=edges2[k][i]=edges2[j][k];
            //     }
            // }
            // cout<<endl;
            // cout<<i<<" "<<j<<":"<<endl;
            // for(int i=1;i<=n;i++){
            //     for(int j=1;j<=n;j++){
            //         cout<<edges2[i][j]<<' ';
            //     }
            //     cout<<endl;
            // }
            //sum
            int res=0;
            for(int r=1;r<=n;r++){
                for(int c=r+1;c<=n;c++){
                    res+=edges2[r][c];
                }
            }
            ans=min(ans,res);
            //cout<<i<<" "<<j<<" "<<res<<endl;
        }
    }
    printf("%d",ans);
    return 0;
}